﻿#include "header.h"

/*

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。

给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：
输入：numCourses = 1, prerequisites = []
输出：[0]
 
提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

*/

// BFS
class Solution1 {
public:
	vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites) {
		vector<vector<int>> adj(numCourses);
		vector<int> indegrees(numCourses);
		vector<int> res;
		for (const auto &node : prerequisites) {
			adj[node[1]].push_back(node[0]);
			++indegrees[node[0]];
		}
		queue<int> q;
		for (int i = 0; i < numCourses; ++i) {
			if (indegrees[i] == 0) q.push(i);
		}
		while (!q.empty()) {
			int temp = q.front();
			q.pop();
			res.push_back(temp);
			--numCourses;
			for (const auto &next : adj[temp]) {
				if (--indegrees[next] == 0) q.push(next);
			}
		}
		return numCourses == 0 ? res : vector<int>();
	}
};

// DFS
class Solution2 {
public:
	vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites) {
		vector<vector<int>> adj(numCourses);
		vector<char> flags(numCourses);
		vector<int> res;
		for (const auto &node : prerequisites) adj[node[1]].push_back(node[0]);
		for (int i = 0; i < numCourses; ++i) {
			if (!dfs(adj, flags, res, i)) return{};
		}
		reverse(res.begin(), res.end());
		return res;
	}
	bool dfs(vector<vector<int>> &adj, vector<char> &flags, vector<int> &res, int n) {
		if (flags[n] == 1) return false;
		if (flags[n] == -1) return true;
		flags[n] = 1;
		for (const auto &next : adj[n]) {
			if (!dfs(adj, flags, res, next)) return false;
		}
		flags[n] = -1;
		res.push_back(n);
		return true;
	}
};
// https://leetcode-cn.com/problems/course-schedule-ii/solution/ke-cheng-biao-ii-by-leetcode-solution/
